package com.qimingyu.array.dynamicarray;

/**
 * 创建动态数组
 * <p>
 * author: cdxyz
 */
public class DynamicArray {
    //动态数组的逻辑上的大小
    int size = 0;
    //动态数组的容量,初始值设置为8
    int capacity = 8;
    //创建一个数组,不赋初始长度，要添加元素的时候再赋值，进行懒加载
    int arr[] = new int[]{};

    /**
     * 动态数组的尾部插入
     *
     * @param value
     */
    public void addLast(int value) {
        expend();
        arr[size] = value;
        size++;
    }

    /**
     * 动态数组的插入
     *
     * @param value
     */
    public void add(int value, int index) {
        expend();
        if (index < 0 || index >= size) {
            try {
                throw new DynamicArrayException("超出动态数组范围！");
            } catch (DynamicArrayException e) {
                System.out.println(e.toString());
                System.exit(-1);
            }
        }
        //先把要插入位置后面的元素整体向右移动一位
        for (int start = size - 1; start >= index; start--) {
            arr[start + 1] = arr[start];
        }
        //再把该元素插入指定位置
        arr[index] = value;
        size++;
    }

    /**
     * 动态数组的删除，删除后返回被删除索引位置的元素的值
     *
     * @param index
     */
    public int delete(int index) {
        if (index < 0 || index >= size) {
            try {
                throw new DynamicArrayException("超出动态数组范围！");
            } catch (DynamicArrayException e) {
                System.out.println(e.toString());
                System.exit(-1);
            }
        }
        int returnValue = arr[index];
        //把所有删除元素整体向左移动一位
        for (int start = index + 1; start < size; start++) {
            arr[start - 1] = arr[start];
        }
        size--;
        return returnValue;
    }

    /**
     * 动态数组的遍历打印
     */
    public void listPrint() {
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * 动态数组的容量检查，容量不足则扩容到原来的1.5倍
     */
    public void expend() {
        if (size == 0) {
            arr = new int[capacity];
        }
        //检查容量是否已满
        if (size == capacity) {
            //创建新数组，容量是原来的1.5倍
            capacity += capacity >> 2;
            int[] newArr = new int[capacity];
            //进行数组拷贝
            System.arraycopy(arr, 0, newArr, 0, size);
            //让arr指向新数组
            arr = newArr;
            System.out.println("数组扩容到：" + capacity);
        }
    }


    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(0);
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);
        dynamicArray.addLast(6);
        dynamicArray.addLast(7);
        dynamicArray.addLast(8);


        dynamicArray.listPrint();

        System.out.println("索引2的位置添加一个6后的动态数组： ");
        dynamicArray.add(6, 2);
        dynamicArray.listPrint();

        System.out.println("索引0的位置删除一个元素后的动态数组： ");
        System.out.println("被删除的元素是：  " + dynamicArray.delete(0));
        dynamicArray.listPrint();
        System.out.print("索引-1的位置删除一个元素后： ");
        dynamicArray.delete(-1);


    }

}
